package 数据结构专栏.B_链表专栏.training;

import 数据结构专栏.B_链表专栏.ListNode;

/**
 * @Title 链表测试手写代码1
 * @Author zhengqiang.tan
 * @Date 2021/5/18 7:50 AM
 */
public class Test1_518 {

    // 1. 删除重复项(0)
    public static ListNode delDuplicate(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = delDuplicate(head.next);
        if (head.val == head.next.val) {
            head = head.next;
        }
        return head;
    }

    // 2. 反转单链表(1)
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode nextNode = head.next;
        head.next = null;
        ListNode res = reverseList(nextNode);
        nextNode.next = head;
        return res;
    }


    // 3. 删除链表种的节点
    public static void delListNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }


    // 4. 判断链表是否有环 (0)
    public static boolean hasLoop(ListNode n) {
        ListNode p1 = n, p2 = n.next;
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        if (p2 == null) return false;
        if (p1.val == p2.val) return true;
        return true;
    }

    // 2
    public static boolean hasLoop2(ListNode n) {
        ListNode slow = n;
        ListNode fast = n;
        while (slow != null && fast != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }


    // 5.合并两个已排序链表
    public static ListNode mergeList(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeList(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeList(l2.next, l1);
            return l2;
        }
    }

    // 6. 求链表倒数第K节点 (0)
    public static ListNode getKNode(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        ListNode fast = head.next, slow = head.next;
        int i;
        for (i = 0; i < k && fast != null; ++i) {
            fast = fast.next;
        }
        if (i < k) return null;

        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }


        return slow;
    }

}
